package com.leetcode.algorithm.y22.m06;

/**
 * 1351. 统计有序矩阵中的负数
 * 
 * https://leetcode.cn/problems/count-negative-numbers-in-a-sorted-matrix/
 * 
 * @author jie.deng
 *
 */
class Question1351Solution01 {

	public int countNegatives(int[][] grid) {
		int m = grid.length;
		int n = grid[0].length;
		return countNegatives(grid, 0, 0, m, n);
	}

	private int countNegatives(int[][] grid, int m0, int n0, int m, int n) {
		int cnt = 0;
		if (m0 >= m || n0 >= n || grid[m - 1][n - 1] >= 0) {
			return 0;
		}
		int left = m0;
		int right = m;
		while (left < right) {
			int mid = left + ((right - left) >> 1);
			if (grid[mid][n0] < 0) {
				right = mid;
			} else {
				left = mid + 1;
			}
		}
		int m1 = left;
		// grid[m1...m)[n0...n)均为负数
		cnt += (m - m1) * (n - n0);

		left = n0;
		right = n;
		while (left < right) {
			int mid = left + ((right - left) >> 1);
			if (grid[m0][mid] < 0) {
				right = mid;
			} else {
				left = mid + 1;
			}
		}
		int n1 = left;
		// grid[m0...m1)[n1...n)均为负数
		cnt += (m1 - m0) * (n - n1);

		// 问题规模缩小了：第m0行和[m1...m)行，以及[n1...n)列已处理
		return cnt + countNegatives(grid, m0 + 1, n0, m1, n1);
	}

}